class Solution:
    def maxEnvelopes(self, envelopes: list) -> int:
        """会超时"""
        if not envelopes:
            return 0
        envelopes.sort(reverse=True)
        envelopes.insert(0, [float("inf"), float("inf")])
        res_list = [0] * len(envelopes)
        for i in range(1, len(envelopes)):
            j = i - 1
            while j >= 0:
                if envelopes[j][0] > envelopes[i][0] and envelopes[j][1] > envelopes[i][1]:
                    res_list[i] = max(res_list[j] + 1, res_list[i])
                j -= 1
        return max(res_list)


class Solution:
    def maxEnvelopes(self, envelopes: list) -> int:
        """不会超时,但是很慢"""
        if not envelopes:
            return 0
        envelopes.sort(reverse=True)
        res_list = [[] for i in range(len(envelopes) + 1)]
        res_list[0].append([float("inf"), float("inf")])
        res = 0
        for i in range(len(envelopes)):
            j, flag = res, False
            while j >= 0:
                for env in res_list[j]:
                    if env[0] > envelopes[i][0] and env[1] > envelopes[i][1]:
                        res_list[j+1].append(envelopes[i])
                        flag = True
                        res = max(res, j + 1)
                        break
                if flag:
                    break
                j -= 1
        return res


class Solution:
    def maxEnvelopes(self, envelopes: list) -> int:
        """反而比上一个慢"""
        if not envelopes:
            return 0
        envelopes.sort(reverse=True)
        envelopes.insert(0, [float("inf"), float("inf")])
        res_list = [[] for i in range(len(envelopes))]
        res_list[0].append(0)
        res = 0
        for i in range(len(envelopes)):
            j, flag = res, False
            while j >= 0:
                for index in res_list[j]:
                    if envelopes[index][0] > envelopes[i][0] and envelopes[index][1] > envelopes[i][1]:
                        res_list[j+1].append(i)
                        flag = True
                        res = max(res, j + 1)
                        break
                if flag:
                    break
                j -= 1
        return res


a = Solution()
print(a.maxEnvelopes([[5, 4], [6, 4], [6, 7], [2, 3]]))
print(a.maxEnvelopes([[1, 2], [2, 3], [3, 4], [3, 5], [4, 5], [5, 5], [5, 6], [6, 7], [7, 8]]))
print(a.maxEnvelopes([[2, 100], [3, 200], [4, 300], [5, 500], [5, 400], [5, 250], [6, 370], [6, 360], [7, 380]]))
print(a.maxEnvelopes([[1, 1]]))
